This application claims priority from European patent application number 99126171.0, filed Dec. 30, 1999, which is hereby incorporated herein by reference in its entirety.
The present invention is generally related to a method and a data processing system for data lookups using high-speed memories. More particularly, the present invention relates to a content addressable memory (CAM) or associative content addressable memory, in such a system.
An associative memory or content addressable memory (CAM) is a memory comprising a plurality of CAM circuits, each comprising a memory circuit and a compare circuit. The CAM is accessed by data content, rather than by the address or location of data.
FIG. 1 shows a block diagram of a CAM according to the prior art comprising a plurality of CAM circuits.
FIG. 2 shows a single CAM circuit of FIG. 1 in more detail.
A known CAM 100 comprises a plurality of identical CAM circuits 109, 110 to 124, such as 16 CAM circuits 0 to 15, and an OR-gate 143, as shown in FIG. 1.
As depicted in FIG. 2, each known CAM circuit 109, 110 to 124 comprises a memory circuit 102 and a compare circuit 106. The memory circuit 102 consists of a memory cell array and the compare circuit 106 comprises a comparator array 126 and a NAND- gate 125. The output of each memory cell (CELL D0 to CELL D31) of the memory circuit 102 is connected with a first input of a corresponding comparator CO 0 to CO 31 in comparator array 126 via output means 104 of the memory circuit 102 and data input means 105 of the compare circuit 106. Compare data C0 to C31, representing the bits of a 32-bit-word, are applied to second inputs of the comparators CO 0 to CO 31 in comparator array 126 via compare data input means 107 of compare circuit 106. The comparators are XOR-gates, i.e. exclusive OR-gates. Via input means 103 of memory circuit 102 input data D0 to D31, also representing the bits of a 32-bit-word, and to be stored in the memory circuit 102, are applied to input means 103 of the memory circuit 102. Each bit of the input data D0 to D31 is stored in a corresponding memory cell of the memory circuit 102, if a write signal is applied to a write line 0 (WL 0) of the CAM circuit 0 (109). The write signal enables writing into the memory cells.
In the following, the operation of known CAM circuit 0 (109) will be described in more detail. It shall be assumed that input data have already been stored in the memory cells of memory circuit 102 in a first step or cycle. Accordingly, each memory cell stores one bit of the input data.
In a second step or cycle, input data D0 to D31 are applied to the input means 103 of memory circuit 102 and a write signal is applied to word line 0 (WL 0) enabling storage of the second input data D0 to D31 in the memory cells (CELL D0 to CELL D31) of the memory circuit 102.
Since it takes a certain time until the first input data stored in said memory circuit 102 are substituted by the applied second input data D0 to D31 in the memory cells, the data status of each memory cell and accordingly of the memory circuit 102 is not defined in the step of storing the second input data D0 to D31. Accordingly, it is necessary to wait a certain time, until the outputs of all memory cells comprise a defined status, i.e. the outputs represent the second input data D0 to D31. Although the waiting period depends on the characteristics of the memory cells, a typical period lasts at least about to the same time it takes to perform a compare operation. This time has to pass before the compare operation can be started and a comparison result may be used for further processing.
Otherwise, it cannot be made sure that a comparison of the data present in memory circuit 102 with the compare data C0 to C31 by the comparator array 126 is a comparison of the second input data D0 to D31 with the compare data C0 to C31.
Each comparator of comparator array 126 generates an output signal indicating whether its applied input bit (0-bit or 1-bit, i.e. a low-level signal or a high-level signal) is identical to its applied compare bit (also a 0-bit or a 1-bit, i.e. a low-level signal or a high-level signal). The output signal or comparison result of each comparator of comparator array 126 is applied to a corresponding input of the NAND-gate 125, which performs a logical AND-operation with the output signals of all comparators and inverts the output signal on the single output line 127 of the NAND-gate 125.
As shown in FIG. 1, each line 127, 128 to 142 of the CAM circuits 0 to 15 is applied to a corresponding input of the OR- gate 143, which comprises a single output line 144 forwarding a match signal generated by at least one of the CAM circuits 0, 1, . . . , 15 (109, 110, . . . , 124) to a data processing system (not shown) comprising the known CAM 100 for further processing.
It is an object of the present invention to provide a more efficient method and data processing system for data lookups.
It is another object of the present invention to provide a method and a data processing system using a content addressable memory, which is more efficient.
It is yet another object of the present invention to provide a method and a data processing system comprising a content addressable memory that performs a comparison of input data and compare data within a lower amount of clock cycles or steps, or within a shorter cycle.